We survey foundational features underlying modern graph query languages. Wefirst discuss two popular graph data models: edge-labelled graphs, where nodesare connected by directed, labelled edges; and property graphs, where nodes andedges can further have attributes. Next we discuss the two most fundamentalgraph querying functionalities: graph patterns and navigational expressions. Westart with graph patterns, in which a graph-structured query is matched againstthe data. Thereafter we discuss navigational expressions, in which patterns canbe matched recursively against the graph to navigate paths of arbitrary length;we give an overview of what kinds of expressions have been proposed, and howthey can be combined with graph patterns. We also discuss several semanticsunder which queries using the previous features can be evaluated, what effectsthe selection of features and semantics has on complexity, and offer examplesof such features in three modern languages that are used to query graphs:SPARQL, Cypher and Gremlin. We conclude by discussing the importance offormalisation for graph query languages; a summary of what is known aboutSPARQL, Cypher and Gremlin in terms of expressivity and complexity; and anoutline of possible future directions for the area.
展开▼
